package com.lfg.leetcode.leetcode200;

public class Trie {

    Element root;


    public Trie() {
        root = new Element();
    }

    public static void main(String[] args) {

        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 true
        System.out.println(trie.search("app"));     // 返回 false
        System.out.println(trie.startsWith("app")); // 返回 true
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 true
    }

    public void insert(String word) {
        Element e = root;
        for (int i = 0; i < word.length(); i++) {
            int pos = word.charAt(i) - 'a';
            Element child = e.children[pos];
            if (null == child) {
                child = new Element();
                e.children[pos] = child;
                e.childrenLen++;
                child.val = word.charAt(i);

            }
            e = child;
        }
        e.cnt++;
    }

    public boolean search(String word) {
        Element e = root;
        for (int i = 0; i < word.length(); i++) {
            int pos = word.charAt(i) - 'a';
            e = e.children[pos];
            if (null == e) {
                return false;
            }
        }
        if (e.cnt > 0) {
            return true;
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        Element e = root;
        for (int i = 0; i < prefix.length(); i++) {
            int pos = prefix.charAt(i) - 'a';
            e = e.children[pos];
            if (null == e) {
                return false;
            }
        }
        return true;
    }

    class Element {
        char val;
        Element[] children = new Element[26];
        int childrenLen;
        int cnt;
    }
}
